/*
 * Copyright (c) 2009-2010 HIT Microelectronic Center
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are
 * met: redistributions of source code must retain the above copyright
 * notice, this list of conditions and the following disclaimer;
 * redistributions in binary form must reproduce the above copyright
 * notice, this list of conditions and the following disclaimer in the
 * documentation and/or other materials provided with the distribution;
 * neither the name of the copyright holders nor the names of its
 * contributors may be used to endorse or promote products derived from
 * this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 *
 * Authors: Gou Pengfei
 *
 * Date:    Dec. 2009
 *
 */

#ifndef __CPU_EDGE_DEP_GRAPH_HH__
#define __CPU_EDGE_DEP_GRAPH_HH__

#include "cpu/edge/comm.hh"

class EdgeCPUImpl;
template<class Impl> class InstructionQueue;
typedef InstructionQueue<EdgeCPUImpl> IQ;

/** Node in a linked list. Each node contains a live producers 
  *   which is followed by all of its live consumers using a list
  *   data structure.
 */
template <class DynInstPtr>
class ProducerEntry
{
   public:
    ProducerEntry()
        : producer(NULL), canForward(false), blockID(0)
    { }

    ~ProducerEntry()
    {
        producer = NULL;
        consumers.clear();
    }

    /** Producer of this entry. */
    DynInstPtr producer;

    /** Flag indicating whether this producer can forward or not. */
    bool canForward;

    /** Block id of this entry. */
    TheISA::BlockID blockID;
    
    /** All the consumers dependent on the producer. */
    std::list<DynInstPtr> consumers;
};

/** Array of linked list that maintains the dependencies between
 * producing instructions and consuming instructions.  Each linked
 * list represents a single physical register, having the future
 * producer of the register's value, and all consumers waiting on that
 * value on the list.  The head node of each linked list represents
 * the producing instruction of that register.  Instructions are put
 * on the list upon reaching the IQ, and are removed from the list
 * either when the producer completes, or the instruction is squashed.
*/
template <class DynInstPtr>
class DependencyGraph
{
  public:
    typedef ProducerEntry<DynInstPtr> DepEntry;
    typedef typename std::list<DepEntry*>::iterator ListIt;

    /** Default construction.  Must call resize() prior to use. */
    DependencyGraph()
        : instQueuePtr(NULL), numEntries(0), memAllocCounter(0), 
             nodesTraversed(0), nodesRemoved(0)
    { }

    ~DependencyGraph();

    /** Resize the dependency graph to have num_entries registers. */
    void resize(int num_entries);

    /** Clears all of the linked lists. */
    void reset();

    /** Set inst queue pointer of this graph. */
    void setInstQueuePtr(IQ * ptr ) {
        instQueuePtr = ptr;
    }

    /** Inserts a producer to the graph. */
    void insertProducer(PhysRegIndex idx, DynInstPtr &new_inst);

    /** Inserts a consumer to the graph. Return TRUE means the inst can be issued immediatly
     *   while FALSE means the inst has been added into the graph, and should wait for dependency.
    */
    bool insertConsumer(PhysRegIndex idx, DynInstPtr &new_inst);

    /** Inserts a consumer to a specific entry of the graph. Return TRUE means the inst can be issued immediatly
     *   while FALSE means the inst has been added into the graph, and should wait for dependency.
    */
    bool insertConsumer(PhysRegIndex idx, ListIt &entry_it,DynInstPtr &new_inst);

    /** Clears the producing instruction. */
    void clearInst(PhysRegIndex idx);

    /** Remove instructions younger than remove_id.  */
    void remove(PhysRegIndex idx, TheISA::BlockID remove_id);

    /** Complete an entry in reg dep graph. Forwarding values from completed write
    *    to already added reads and mark this entry as able to farward.
    */
    void complete(PhysRegIndex idx, DynInstPtr complete_inst);

    /** Commit an entry and remove it.*/
    void commit(PhysRegIndex idx, DynInstPtr commit_inst );

    /** Checks if there are any dependents on a specific register. */
    bool empty(PhysRegIndex idx) { return !dependGraph[idx].empty(); }

    /** Debugging function to dump out the dependency graph.
     */
    void dump();

  private:
    /** Array of linked lists.  Each linked list is a list of all the
     *  instructions that depend upon a given register.  The actual
     *  register's index is used to index into the graph; ie all
     *  instructions in flight that are dependent upon r34 will be
     *  in the linked list of dependGraph[34].
     */
    std::vector < std::list < DepEntry* > > dependGraph;

    IQ *instQueuePtr;
    
    /** Forwarding from producer to consumer. */
    void forward(DynInstPtr &producer, DynInstPtr& consumer);
    
    /** Number of linked lists; identical to the number of registers. */
    int numEntries;

    // Debug variable, remove when done testing.
    unsigned memAllocCounter;

  public:
    // Debug variable, remove when done testing.
    uint64_t nodesTraversed;
    // Debug variable, remove when done testing.
    uint64_t nodesRemoved;
};

template <class DynInstPtr>
DependencyGraph<DynInstPtr>::~DependencyGraph()
{
    dependGraph.clear();
}

template <class DynInstPtr>
void
DependencyGraph<DynInstPtr>::resize(int num_entries)
{
    numEntries = num_entries;
    dependGraph.resize(numEntries);
}

template <class DynInstPtr>
void
DependencyGraph<DynInstPtr>::reset()
{
    DepEntry * ptr = NULL;
    // Clear the dependency graph
    
    for (int i = 0; i < numEntries; ++i) {

        while (!dependGraph[i].empty()) {
            memAllocCounter--;

            ptr = dependGraph[i].front();
            ptr->producer = NULL;
            (ptr->consumers).clear();

            delete ptr;
            dependGraph[i].pop_front();
        }
    }
}

template <class DynInstPtr>
void
DependencyGraph<DynInstPtr>::insertProducer(PhysRegIndex idx, 
                                     DynInstPtr &new_inst)
{
    // Only reg-write inst can be producer.
    assert(new_inst->isWrite());
    assert(instQueuePtr);

    // Create an entry, add it to tail of the list.
    DepEntry *new_entry = new DepEntry;
    
    new_entry->producer = new_inst;
    new_entry->blockID = new_inst->getBlockID();
    
    DPRINTF(EdgeRegDep, "Creating a depend entry, adding it into producer list.\n" );

    if (!dependGraph[idx].empty()) {                 
        // The younger block should be in the tail of the list.
        assert((dependGraph[idx].back())->blockID < new_inst->getBlockID());
    }

    dependGraph[idx].push_back(new_entry);
        
    ++memAllocCounter;    
}

template<class DynInstPtr>
bool
DependencyGraph<DynInstPtr>::insertConsumer(PhysRegIndex idx,
                                     DynInstPtr &new_inst)
{
    // Only reg-read inst should be the consumer
    assert(new_inst->isRead());
    assert(instQueuePtr);

    if (dependGraph[idx].empty()) {
        DPRINTF(EdgeRegDep, "Read inst has no producer.\n");
        return true;
    }
    
    ListIt curr = dependGraph[idx].end();
    ListIt begin = dependGraph[idx].begin();
    TheISA::BlockID bid = new_inst->getBlockID();

    --curr;
    // Find the last old write entry.
    do{
    
        if ((*curr)->blockID < bid) {
        
            if (!(*curr)->canForward) {
                DPRINTF(EdgeRegDep, "Adding consumer to dep graph.\n");
                
                ((*curr)->consumers).push_back(new_inst);
                return false;
            } else {
                DPRINTF(EdgeRegDep, "Forwarding from write inst. \n");
                
                this->forward((*curr)->producer, new_inst);
                return true;
            }
        }
        
    } while ((curr--) != begin);
     // Here means no producer entry matchs.
    return true;
}

template<class DynInstPtr>
bool
DependencyGraph<DynInstPtr>::insertConsumer(PhysRegIndex idx,
                                     ListIt &entry_it,DynInstPtr &new_inst)
{
    // Only reg-read inst should be the consumer
    assert(new_inst->isRead());
    assert(instQueuePtr);
    //assert(entry_it);
    assert(!dependGraph[idx].empty());
         
    assert((*entry_it)->blockID < new_inst->getBlockID());
        
    if (!(*entry_it)->canForward) {
        DPRINTF(EdgeRegDep, "Adding consumer to dep graph.\n");
        
        ((*entry_it)->consumers).push_back(new_inst);
        return false;
    } 
    
    DPRINTF(EdgeRegDep, "Forwarding from write inst. \n");
    
    this->forward((*entry_it)->producer, new_inst);
    return true;

}

template<class DynInstPtr>
void
DependencyGraph<DynInstPtr>::forward(DynInstPtr &producer, 
                                     DynInstPtr &consumer)
{
    // Reg-write can be producer and Reg-read can be consumer
    assert(producer->isWrite());
    assert(consumer->isRead());

    DPRINTF(EdgeRegDep, "Forwarding from producer[Bid:%lli][Iid:%lli]"
                               " to consumer[Bid:%lli][Iid:%lli].\n",
                               producer->getBlockID(),
                               producer->getInstID(),
                               consumer->getBlockID(),
                               consumer->getInstID());
                               
    consumer->setRegForward(producer->getIntIQOperand(0));
}

template <class DynInstPtr>
void
DependencyGraph<DynInstPtr>::remove(PhysRegIndex idx,
                                    TheISA::BlockID remove_id)
{
    if(dependGraph[idx].empty()){
        DPRINTF(EdgeRegDep, "Nothing to remove in reg dep graph.\n");
        return;
    }
    
    ListIt curr = dependGraph[idx].end();
    ListIt begin = dependGraph[idx].begin();
    --curr;

    do{
        if ((*curr)->blockID <= remove_id) {
            // Find a entry is not supposed to be removed.
            // Check its consumer list to find consuemrs that
            // should be removed.
            while (!((*curr)->consumers ).empty()) {
                if (((*curr)->consumers ).back()->getBlockID() > remove_id) {
                    // Find a consumer that should be removed.
                    ((*curr)->consumers).pop_back();
                    continue;
                }
                // Because this list is sequenced in block age, 
                // we should stop search consumer list here.
                break;
            }
            // We can hit an older entry only once, so break here.
            break;
        }

        // Find a younger entry, remove it.
        (*curr)->producer = NULL;
        ((*curr)->consumers).clear();
        delete (*curr);
        dependGraph[idx].erase(curr);
        --memAllocCounter;
        
    } while ((curr--) != begin);
    
    return;
}

template <class DynInstPtr>
void
DependencyGraph<DynInstPtr>::complete(PhysRegIndex idx, 
                                     DynInstPtr complete_inst )
{
    // Only reg-write inst can complete in reg dep graph.
    assert(complete_inst->isWrite());
    // Only completed reg-write inst can reach here.
    assert(complete_inst->isExecuted());
    // Something should be places into list.
    assert(!dependGraph[idx].empty());
    // Inst queue pointer should have been initialized.
    assert(instQueuePtr);
    
    ListIt curr = dependGraph[idx].begin();
    ListIt end = dependGraph[idx].end();

    DPRINTF(EdgeRegDep, "Complete reg-write to reg[%i] in reg dep graph.\n",
                                                                 idx);

    while (curr != end) {
        if ((*curr)->producer->seqNum == complete_inst->seqNum) {
            assert((*curr)->blockID == complete_inst->getBlockID());

            if (complete_inst->isNullified()) {
                // Check to see whether it's the head producer 
                // has been nullified.
                // If it's the head producer, we're safe to wake
                // all it's consumer. If not, we should check 
                // the producer list to see whether there's an
                // elder producer or not. The consumers of the 
                // nullified producer should be added to the 
                // elder producer to guarantee the register 
                // dependency.
                if (curr == dependGraph[idx].begin()) {
                    // Head producer is nullified,
                    // wake consumers without forwarding.
                    while(!((*curr)->consumers).empty()){
                        DynInstPtr consumer = (*curr)->consumers.front();
                        
                        consumer->setCanIssue();
                        //consumer->setReadRegIssuing();
                        this->instQueuePtr->addIfReady(consumer);
                        ((*curr)->consumers).pop_front();
                    }
                } else {
                    // Not the head, find the elder producer.
                    ListIt entry_it = curr;
                    --entry_it;
                    while(!((*curr)->consumers).empty()) {
                        DynInstPtr consumer = (*curr)->consumers.front();

                        if (insertConsumer(idx,entry_it,consumer)) {
                            // This producer can forward, mark the 
                            // consumer as issuable.
                            consumer->setCanIssue();
                            //consumer->setReadRegIssuing();
                            this->instQueuePtr->addIfReady(consumer);
                        } 
                        ((*curr)->consumers).pop_front();
                    }
                }
                
                // commit it immediatly.
                this->commit(idx, complete_inst);
                return;
            }
            
            // Matched entry, set it as able to forward. 
            (*curr)->canForward = true;
            // Wake consumers
            while (!((*curr)->consumers).empty()) {
                DynInstPtr consumer = (*curr)->consumers.front();
                
                this->forward((*curr)->producer, consumer);
                consumer->setCanIssue();
                //consumer->setReadRegIssuing();
                this->instQueuePtr->addIfReady(consumer);
                ((*curr)->consumers).pop_front();
            }
            // Only one inst can be matched.
            return;
        }
        ++curr;
    }

    assert(0&&"Complete non existed inst in reg dep graph.");
}

template<class DynInstPtr>
void
DependencyGraph<DynInstPtr>::commit(PhysRegIndex idx, 
                                      DynInstPtr commit_inst)
{
    // Only reg-write inst can complete in reg dep graph.
    assert(commit_inst->isWrite());
    // Only reg-write inst that has been both in executed and block
    // completed status could be commited in dep reg graph.
    assert(commit_inst->isExecuted() && 
           (commit_inst->isNullified() || commit_inst->isBlockCompleted()));

    ListIt curr = dependGraph[idx].begin();
    ListIt end = dependGraph[idx].end();

    while (curr != end) {
        if ((*curr)->producer->seqNum == commit_inst->seqNum) {
            // Consumer list should be empty because it should
            // have been cleaned when the entry complete.
            assert(((*curr)->consumers).empty());

            (*curr)->producer = NULL;
            delete (*curr);
            dependGraph[idx].erase(curr);
            --memAllocCounter;

            // We are supposed to find only one entry in this list,
            // so break here.

            return;
        }
        // The committed entry should always in the head 
        // of entry list in EDGE architecture. However, I don't
        // intend to enforce this due to some special concerns.
        DPRINTF(EdgeRegDep, "Commit inst is not in the head of entry list.\n" );
        ++curr;
    }

    assert(0&&"Commit non-existed inst in reg dep map.");
}

template <class DynInstPtr>
void
DependencyGraph<DynInstPtr>::dump()
{
    ListIt curr;
    ListIt end;

    for (int i = 0; i < numEntries; ++i)
    {
        if (dependGraph[i].empty()) {
            cprintf("dependGraph[%i] has no producer.\n");
            continue;
        }
        
        curr = dependGraph[i].begin();
        end = dependGraph[i].end();

        while (curr != end) {

            if ((*curr)->producer) {
                cprintf("dependGraph[%i]: producer: %#x [Bid:%lli][Iid:%lli] consumer: ",
                        i, (*curr)->producer->readPC(), 
                        (*curr)->producer->getBlockID(),
                        (*curr)->producer->getInstID());
            } else {
                cprintf("dependGraph[%i]: Invalid entry: consumer:", i);
            }

            typename std::list<DynInstPtr>::iterator c_curr = (curr->consumers).begin();
            typename std::list<DynInstPtr>::iterator c_end = (curr->consumers).end();
            
            while (c_curr != c_end) {
            
                cprintf("%#x [Bid:%lli][Iid:%lli] ",
                        (*c_curr)->readPC(), 
                        (*c_curr)->getBlockID(),
                        (*c_curr)->getInstID());

                ++c_curr;
            }

            cprintf("\n");
        }
    }
    cprintf("memAllocCounter: %i\n", memAllocCounter);
}

#endif // __CPU_EDGE_DEP_GRAPH_HH__
